package com.learn.algorithm_938;

import com.dataconsruct.TreeNode;

import java.util.Objects;

/**
 * 二叉搜索树的范围和
 * https://leetcode-cn.com/problems/range-sum-of-bst/
 *
 * @author gatts, 2022/1/12 11:57
 */
public class SearchTreeNodeRange {

    public static void main(String[] args) {
        /*
          输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
          输出：32
        */
        TreeNode root = new TreeNode(10);
        TreeNode L1 = new TreeNode(5);
        TreeNode R1 = new TreeNode(15);
        root.left = L1;
        root.right = R1;
        L1.left = new TreeNode(3);
        L1.right = new TreeNode(7);
        R1.left = null;
        R1.right = new TreeNode(18);

        int low = 7;
        int high = 15;
        System.out.println(new SearchTreeNodeRange().rangeSumBST(root, low, high));
    }

    public int rangeSumBST(TreeNode root, int low, int high) {
        // 为空，再见
        if (root == null) {
            return 0;
        }
        // 只看root右子树
        else if (root.val < low) {
            return rangeSumBST(root.right, low, high);
        }
        // 只看root左子树
        else if (root.val > high) {
            return rangeSumBST(root.left, low, high);
        }
        // 在 low - high范围
        else {
            System.out.println("计数：" + root.val);
            // 返回当前节点值，并递归计算左右子树
            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
        }
    }

}

